home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7645 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.4 KB
  1. Path: mail2news.demon.co.uk!genesis.demon.co.uk
  2. From: Lawrence Kirby <fred@genesis.demon.co.uk>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: merge algorithm
  5. Date: Tue, 27 Feb 96 22:46:48 GMT
  6. Organization: none
  7. Message-ID: <825461208snz@genesis.demon.co.uk>
  8. References: <312CEE69.842@onyx.idbsu.edu> <4gljrl$auj@sun001.spd.dsccc.com>
  9. Reply-To: fred@genesis.demon.co.uk
  10. X-NNTP-Posting-Host: genesis.demon.co.uk
  11. X-Newsreader: Demon Internet Simple News v1.27
  12. X-Mail2News-Path: genesis.demon.co.uk
  13.  
  14. In article <4gljrl$auj@sun001.spd.dsccc.com>
  15.            jmccarty@spd.dsccc.com "Mike McCarty" writes:
  16.  
  17. >In article <312CEE69.842@onyx.idbsu.edu>,
  18. >Joe E. Coffland <jcofflan@onyx.idbsu.edu> wrote:
  19. >)I am trying to find an algorithm to merge two sorted arrays containing
  20. >)n elements.
  21. >)ie. A[1] <= A[2]<= ... <= A[m] and A[m+1] <= A[m+2] <= ... <A[n]
  22. >)The algorithm must run in O(n) time and require only a small amount of
  23. >)fixed additional memory regardless of the size of m or n. I have reason
  24. >)to believe that there is such an algorithm but I have only been able to
  25. >)find algorithms that meet the memory restriction but run in at best
  26. >)O(nlogn) and are recursive (which can through some work of course be
  27. >)changed in to an iterative algorithm). If any one can point me to a book
  28. >)or any other source of information on the subject or just get me headed
  29. >)in the right direction it would be greatly appriciated.
  30.  
  31. As far as I am aware there is no such algorithm although I'd be very
  32. happy to be proved wrong. One obvious O(nlogn) algorithm is heapsort.
  33.  
  34. >Won't a simple exchange algorithm work? Start with pointers into the
  35. >left and right halves. Advance the left pointer until you find an
  36. >element larger than the right pointer data. Exchange the left pointer
  37. >data with the right pointer data. Advance the left pointer etc. When you
  38. >have gone through the entire data set, there is only one output array.
  39.  
  40. Unfortunately this doesn't work. As soon as you do the first exchange the
  41. elements of the 'right' array are no longer guaranteed sorted so the
  42. algorithm breaks down. 'Fixing' this raises the algorithm order.
  43.  
  44. This is an interesting challenge - if it was solved it would make merge
  45. sort a good candidate for a qsort() implementation.
  46.  
  47. -- 
  48. -----------------------------------------
  49. Lawrence Kirby | fred@genesis.demon.co.uk
  50. Wilts, England | 70734.126@compuserve.com
  51. -----------------------------------------
  52.